package com.gzl.exercise;

import org.junit.jupiter.api.Test;

import java.util.Arrays;

/**
 * @PROJECT_NAME: exercise
 * @NAME: 轮转数组
 * @DESCRIPTION: 中等
 * @USER: gaozengliang
 * @DATE: 2023/3/28
 */
public class 轮转数组 {
    /**
     * 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
     *
     * 示例 1:
     * 输入: nums = [1,2,3,4,5,6,7], k = 3
     * 输出: [5,6,7,1,2,3,4]
     * 解释:
     * 向右轮转 1 步: [7,1,2,3,4,5,6]
     * 向右轮转 2 步: [6,7,1,2,3,4,5]
     * 向右轮转 3 步: [5,6,7,1,2,3,4]
     *
     * 示例 2:
     * 输入：nums = [-1,-100,3,99], k = 2
     * 输出：[3,99,-1,-100]
     * 解释:
     * 向右轮转 1 步: [99,-1,-100,3]
     * 向右轮转 2 步: [3,99,-1,-100]
     *
     * 提示：
     * 1 <= nums.length <= 10^5
     * -2^31 <= nums[i] <= 2^31 - 1
     * 0 <= k <= 10^5
     *
     * 进阶：
     * 尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
     * 你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
     */

    /**
     * 在原数组操作，环形替换  数学运算
     *
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/rotate-array/solutions/551039/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/
     * 来源：力扣（LeetCode）
     */
    void rotate3(){}

    /**
     * 在原数组操作，数组翻转。
     * 该方法基于如下的事实：
     * 当我们将数组的元素向右移动 k 次后，尾部 k mod n个元素会移动至数组头部，其余元素向后移动 k mod n 个位置。
     * 我们可以先将所有元素翻转，这样尾部的 k mod n 个元素就被移至数组头部，但是此时全部都是翻转的，需要再次翻转回来。
     * 然后我们再翻转 [0,k mod n−1] 区间的元素和 [k mod n,n−1] 区间的元素即能得到最后的答案。
     * 如 [1,2,3,4,5,6,7]，n=7,k=3;
     * 首先翻转所有：[7,6,5,4,3,2,1]，此时尾部 3 个元素已经到了头部，
     * 接下来再分别把 数组 [0,2] 区间和 [3,6] 区间的元素翻转过来就是我们要的答案
     */
    @Test
    void rotate2() {
        int[] nums = {1,2,3,4,5,6,7};
        int k = 3;

        int n = nums.length;
        k %= n;
        reverse(nums, 0, n - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, n - 1);
        System.out.println(Arrays.toString(nums));
    }

    void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }

    // 使用额外数组
    @Test
    void rotate1(){
        int[] nums = {1,2,3,4,5,6,7};
        int k = 3;

        int n = nums.length;
        k = k % n;
        if (k == 0) {
            return;
        }
        int[] moves = new int[n];
        for (int i=0;i<n;i++){
            moves[(i+k)%n] = nums[i];
        }
//        nums = moves;
        // 复制数组
        System.arraycopy(moves, 0, nums, 0, n);

        for (int num : nums){
            System.out.print(num+",");
        }
    }
}
